<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="utf-8">
    <title>字典树 - GO的实现</title>
  
    <meta name="author" content="秀才">

    <!-- Le HTML5 shim, for IE6-8 support of HTML elements -->
    <!--[if lt IE 9]>
      <script src="http://html5shim.googlecode.com/svn/trunk/html5.js"></script>
    <![endif]-->

    <!-- Le styles -->
    <link href="/assets/twitter/stylesheets/bootstrap.min.css" type="text/css" rel="stylesheet" media="all">
<link href="/assets/twitter/stylesheets/style.css" type="text/css" rel="stylesheet" media="all">
 
    <link href="/assets/twitter/widgets/google_prettify/stylesheets/twitter-bootstrap.css" type="text/css" rel="stylesheet" media="all">

    <!-- Le fav and touch icons -->
  <!-- Update these with your own images
    <link rel="shortcut icon" href="images/favicon.ico">
    <link rel="apple-touch-icon" href="images/apple-touch-icon.png">
    <link rel="apple-touch-icon" sizes="72x72" href="images/apple-touch-icon-72x72.png">
    <link rel="apple-touch-icon" sizes="114x114" href="images/apple-touch-icon-114x114.png">
  -->
  </head>

  <body>

    <div class="navbar">
      <div class="navbar-inner">
        <div class="container">
          <a class="brand" href="/">秀才</a>
          <ul class="nav">
            
              


  <li><a href="/tags">标签</a></li>


            
              


  <li><a href="/categories">分类</a></li>


            
              


  <li><a href="/about">关于我</a></li>


            
          </ul>
        </div>
      </div>
    </div>

    <div class="container">
      <div class="content">
        <div class="page-header">
  <h1>字典树 - GO的实现 </h1>
</div>

<div class="row">
  <div class="span12">
    <h3>字典树简介</h3>

<p>百度百科这么介绍：</p>

<p>​   又称单词查找树，<a href="https://baike.baidu.com/item/Trie%E6%A0%91">Trie树</a>，是一种<a href="https://baike.baidu.com/item/%E6%A0%91%E5%BD%A2%E7%BB%93%E6%9E%84">树形结构</a>，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的<a href="https://baike.baidu.com/item/%E5%AD%97%E7%AC%A6">字符</a>串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高</p>

<h3>GO版本的字典树</h3>

<p>目标：实现敏感词汇的过滤。</p>

<pre><code class="language-go">var (
	badwordTree *TrieTree
)

type TrieTree struct {
	Root *trieNode `json:&quot;root&quot;`
}

type trieNode struct {
	Children map[rune]*trieNode `json:&quot;children&quot;`
  	// done 表示是否是最后一个词
	Done     bool               `json:&quot;done&quot;`
}

// rune保证汉字的下标更加准确
func BuildTree(words [][]rune) (tree *TrieTree) {
	tree = &amp;TrieTree{
		Root: &amp;trieNode{
			Children: make(map[rune]*trieNode),
		},
	}

	for _, word := range words {
		tree.Root.insertWord(word)
	}
	return
}

// 目标：查找出敏感词，并用mask替换，例如毛爷爷替换成毛**
func (tree *TrieTree) ReplaceAllMatch(targetStr string, mask rune) string {
	target := []rune(targetStr)
	cur := 0
	length := len(target)
	// 每次循环，如果查找一个敏感词就标记，如果没找到就continue
	for cur &lt; length {
		node := tree.Root
		length2 := 0
		for j := cur; j &lt; length; j++ {
			tmp, found := node.Children[target[j]]
			if found {
				node = tmp
				// 如果是敏感词的最后一个字，则标记
				if node.Done {
					length2 = j - cur + 1
				}
			} else {
				break
			}
		}
		// 如果标记了敏感词，则逐字替换
		if length2 &gt; 0 {
			for i := 0; i &lt; length2; i++ {
				target[cur+i] = mask
			}
			cur = cur + length2
		} else {
			cur++
		}
	}
	return string(target)
}

func (node *trieNode) insertWord(word []rune) {
	cur := node
	for _, char := range word {
		cur = cur.findOrCreate(char)
	}
	cur.Done = true
}

func (node *trieNode) find(char rune) (child *trieNode) {
	child, _ = node.Children[char]
	return
}

var skips = []rune{' ', '.', '-', '*', '#', '@', ',', '/', '=', '_'}

func (node *trieNode) findOrCreate(char rune) (child *trieNode) {
	child, found := node.Children[char]
	if !found {
		child = &amp;trieNode{
			Children: make(map[rune]*trieNode, 4),
		}
		node.Children[char] = child
		for _, skip := range skips {
			child.Children[skip] = child
		}
	}
	return
}

// 加载配置文件，并创建字典树
func LoadBadwordTree() (err error) {
	content, err := ioutil.ReadFile(&quot;./conf/xxxx.json&quot;)
	if err != nil {
		log.Fatal(&quot;ReadFile:&quot;, err)
	}
	rawWords := make([]string, 0)
	err = json.Unmarshal(content, &amp;rawWords)
	if err != nil {
		log.Fatal(&quot;Unmarshal:&quot;, err)
	}
	words := make([][]rune, len(rawWords))
	for i, word := range rawWords {
		words[i] = []rune(word)
	}
	badwordTree = BuildTree(words)
	return
}

// 暴露的方法
func WordFilter(targetStr string, mask rune) string {
	return badwordTree.ReplaceAllMatch(targetStr, mask)
}

</code></pre>

    <hr>
    <div class="pagination">
      <ul>
        <ul>
          
            <li class="prev"><a href="/mongodb/mongodb-%E6%85%A2%E6%9F%A5%E8%AF%A2/" title="mongodb 慢查询">&larr; Previous</a></li>
          
          

            <li><a href="/archive">Archive</a></li>

          
            <li class="next"><a href="/go/go-%E6%A0%87%E5%87%86%E5%8C%85%EF%BC%9Afmt/" title="go 标准包：fmt">Next &rarr;</a></li>
          
          
        </ul>
      </ul>
    </div>
    <hr>
    
  </div>
  
  <!-- <div class="span4">
    <h4>Published</h4>
    <div class="date"><span>2017-12-27</span></div>
    <br>
    <h4>Categories</h4>
    <ul class="tag_box">
    
      <li>
  <a href="/categories/#go-ref">go <span>7</span></a>
</li>
    
    </ul>
    <br>
    <h4>Tags</h4>
    <ul class="tag_box">
    
      <li>
  <a href="/tags/#go-ref">go <span>7</span></a>
</li>
    
      <li>
  <a href="/tags/#%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95-ref">数据结构与算法 <span>1</span></a>
</li>
    
    </ul>
  </div> -->
</div>

      </div>

      <footer>
        <p>&copy; 秀才 2013 
          with help from <a href="http://github.com/wendal/gor" target="_blank" title="Gor -- Fast Blog">Gor</a>
          and <a href="http://twitter.github.com/bootstrap/" target="_blank">Twitter Bootstrap</a>
		  and Idea from <a href="http://ruhoh.com" target="_blank" title="The Definitive Technical Blogging Framework">ruhoh</a>
        </p>
      </footer>

    </div> <!-- /container -->
    <!-- <script src="//cdnjscn.b0.upaiyun.com/libs/prettify/r298/prettify.min.js"></script> -->
    <script src="http://cdn.staticfile.org/prettify/r298/prettify.min.js"></script>
    <script>
      var pres = document.getElementsByTagName("pre");
      for (var i=0; i < pres.length; ++i) {
        pres[i].className = "prettyprint linenums";
      }
      prettyPrint();
    </script>
    
    
  </body>
</html>
